//
// Created by 123 on 2024/3/4.
//
#include <iostream>

using namespace std;

typedef struct LinkNode {
    int data;
    LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

//初始化
void initQueue(LinkQueue &l);

//判空
bool isEmpty(LinkQueue l);

//进队列
bool enQueue(LinkQueue &l, int e);

//出队列
bool deQueue(LinkQueue &l, int &e);

//获取头
bool getHead(LinkQueue l, int &e);

void show(LinkQueue l);

int main() {

    LinkQueue l;
    initQueue(l);
    show(l);
    cout << isEmpty(l) << "==========" << endl;

    enQueue(l, 1);
    show(l);
    enQueue(l, 2);
    show(l);
    enQueue(l, 3);
    show(l);
    enQueue(l, 4);
    show(l);
    cout << isEmpty(l) << "==========" << endl;
    int e = -1;
    deQueue(l, e);
    cout << e << "     <--------" << endl;
    show(l);
    deQueue(l, e);
    cout << e << "     <--------" << endl;
    show(l);
    deQueue(l, e);
    cout << e << "     <--------" << endl;
    show(l);
    deQueue(l, e);
    cout << e << "     <--------" << endl;
    show(l);
    cout << isEmpty(l) << "==========" << endl;
    enQueue(l, 1);
    show(l);
    cout << isEmpty(l) << "==========" << endl;


    cout << getHead(l, e) << "         +++++++++++   " << e << "   ++++" << endl;
    show(l);
    deQueue(l, e);
    cout << e << "     <--------" << endl;
    show(l);
    cout << getHead(l, e) << "         +++++++++++   " << e << "   ++++" << endl;
    show(l);


}

//初始化
void initQueue(LinkQueue &l) {
    l.front = l.rear = (LinkNode *) malloc(sizeof(LinkNode));
    l.front->next = NULL;
}

//判空
bool isEmpty(LinkQueue l) {
    return l.front == l.rear;
}

//进队列
bool enQueue(LinkQueue &l, int e) {
    LinkNode *node = (LinkNode *) malloc(sizeof(LinkNode));
    node->data = e;
    node->next = NULL;
    l.rear->next = node;
    l.rear = node;
    return true;
}

//出队列
/**
 * 出队列时，一定要记得释放内存，凡是用 malloc 函数申请的内存
 * 都是在堆里，需要手动释放
 * @param l
 * @param e
 * @return
 */
bool deQueue(LinkQueue &l, int &e) {
    if (l.front == l.rear)
        return false;
//    e=l.front->next->data;
//    if (l.front->next->next==NULL){
//        l.front->next=NULL;
//        l.rear=l.front;
//    }else{
//        l.front->next=l.front->next->next;
//    }
    //此种实现方式更为精简
    LinkNode  *node=l.front->next;
    e=node->data;
    l.front=node->next;
    if(l.rear==node)
        l.rear=l.front;
    free(node);
    return true;
}

//获取头
bool getHead(LinkQueue l, int &e) {
    if (l.front == l.rear)
        return false;
    e = l.front->next->data;
    return true;
}

void show(LinkQueue l) {
    LinkNode *node = l.front;
    while (node->next != NULL) {
        cout << node->next->data << "    ";
        node = node->next;
    }
    cout << endl;
}


